Java from char to String

Posted on | Edited on | | Views:

There is always a corresponding wrapper class for each primitive type in Java, and all wrapper classes are IMMUTABLE. Then what is a wrapper class for?

  • Can be used in Java generic, for example, the obect in List<Object> are wrapper class of primitive type.
  • Can be used to define and add member function.
  • Can be represented by null if not exists.

E.g. char --> Character

Article Langauge: Chinese
Example Langauge: Java
Reading Time: 17min

Char

在 Java 中, char 是 primitive 类型, String 则是一个类.
Java 中, 一个 char (primitive type) 使用的是 Unicode, 所以是 16 位的(2bytes).

  • 前 128(0~127) 个 和 ascii 码是重复的.
  • 前 3 个和第 128 个是不可打印的( debug 时候要注意, 可以打印 int.)
  • ‘0’ ~ ‘9’, ‘a’ ~ ‘z’, ‘A’ ~ ‘Z’是连续排列的. 所以可以通过+/-操作来得到他们的值, 或者在位置.

char 常用的操作:

  • char - ‘0’ char –> int
  • char - ‘a’ char –> int(position after’a’ in the unicode chart)
  • char - ‘A’ char –> int(position after’A’ in the unicode chart)
  • cahr - ‘a’ + ‘A’ lower –> upper
  • cahr - ‘A’ + ‘a’ upper –> lower
  • (int)char char –> unicode
  • (char)int int(unicode) –> char

String

每一个 string 的类里面都有一个 final char[] value, int offset, 和 int count.
offset 作为一个优化的存在, 多数应用于得到一个 String 的 substring (从下标为 index 的元素出发, 数 count 个元素).

String 的构造函数:

  • String()
  • String(“value”)
  • String(char[] array)
  • String(char[] array, int offset, int count)
  • String(StringBuilder)

_当涉及到一个 string 的长度变化的时候多数建议用 StringBuilder 而不是用 Concatenation(直接加). 对于 n 个长度为 m 的数组来说, concatenate 的时间复杂度是 O(n^2 _ m). 因为 m + m –> 2m + m –> 3m + m ….–> nm + m = (1 + 2 + 3….+ n) _ m = n^2 _ m (每一次相加的时候都会新建一个对象).
而 StringBuilder 内部实现是一个长度动态变化的 char[]. Amortized time complexity 是 O(1)的, 所以 n 个 长度为 m 的数组相加就是 O(nm).*

substring 的 api:

  • str.substring(start, end) //包含 start 不包含 end
  • str.substring(start) //从 start 到最后

相较于 Java 7u6 来说, 新的版本直接创建了一个新的 substring 的对象, 不重复使用原来的 string, 时间上更快一些. 而 7u6 之前的版本创建空间上重复使用了原来的 string, 创建时间更快一些, 但是使用起来的时间复杂度是 O(n). 因为 reference 指向的是原来 string 地址的起始位置.

常用的转换成 String 的方法:

  • primitive type: value + ""
  • wrapper class: String.valueOf(value) //避免 NPE

String 转换成其他类型(例如 Integer):

  • Integer.valueOf(value)
  • Integer.parseInt(value)

String 常用的一些的比较和判断的 api:

  • boolean endsWith("suffix")
  • boolean startsWith("prefix")
  • int compareTo("anotherString") //lexicographical order
  • int compareToIgnoreCase("string")
  • boolean equals(Object)
  • boolean equalsIgnoreCase("string")

一些其他的常用 api:

  • boolean contains(“char sequence”)
  • String[] split(“regex”)
  • String[] split(“regex”, limitNumber)
  • String trim()
  • String toLowerCase()
  • String toUpperCase()
  • int indexOf(unicode#) //param 类型是 int, 这里面通常直接使用一个 char, 只是自动进行了一个类型转换.
  • int lastIndexOf(‘char’)
    etc.

StringBuilder 的常用 api:2

  • append(‘char’) //O(1)
  • append(“String”) //O(n)

这里面, 返回类型是 String 的方法都不是 inplace 的操作, 因为 String 是 immutable 的类型. 所以时间复杂度都是 O(n)的, 因为要重新创建一个对象1.

Parse a String into Integer (乞丐版 atoi)

input: A String with only positive numbers.
output: The position integer, which the string represents.

最基本的 char –> int 的应用. 代码如下:

1
2
3
4
5
6
7
8
9
10
11
public int parsInt(String str) {
	if (str == null || str.length() == 0) {
		throw new IllegalArgumentException("Invalid input.");
	}

	int result = 0;
	for (char ch : str.toCharArray()) {
		result = result * 10 + (ch - '0');
	}
	return result;
}

Atoi

input: A String with all characters that can make a valid integer.
output: The integer.

Corner cases:

  • Null/Empty input
  • Leading space
  • Signs(+ / -)
  • Overflow

其实和就是多了一些 corner case. 可以先把基础代码写进去, 然后逐渐添加解决方案. 代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int parsInt(String str) {
	if (str == null || str.length() == 0) {
		throw new IllegalArgumentException("Invalid input.");		//null/empty input
	}

	str = str.trim();												//leading/trailing space

	boolean positive = true;										//sign.
	int i = 0;
	while (i < str.length()) {
		if (str.charAt(i) == '-' || str.charAt(i) == '+') {
			positive = str.charAt(i) == '+';
			i++;													//If it has a sign, whether it's '-' or '+', index needs to move rightward.
		}
	}


	//int result = 0;
	long result = 0;												//overflow
	for (; i < input.length; i++) {
		result = result * 10 + (ch - '0');
		if (result > (long)Integer.MAX_VALUE + 1) {					//MAX_VALUE + 1 = abs(MIN_VALUE);
			break;
		}
	}
	result = positive ? result : result * -1;						//adding sign
	if (result > (long)Integer.MAX_VALUE) return Integer.MAX_VALUE;
	if (result < (long)Integer.MIN_VALUE) return Integer.MIN_VALUE;
	return (int) result;
}

Valid Numeric

input: A string.
output: Whether the string is a valid numeric.

Corner cases:

  • Null/empty input
  • Leading/trailing space
  • Leading 0s
  • Decimal point
  • Sign -/+
  • Scientific notation (e/E)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isValid(String str) {
	if (str == null || str.length() == 0) {
		return false;
	}

	String pattern = "[-+]?(([0-9]+(\.[0-9]*)?)|\.[0-9]+)([eE][-+]?[0-9]+)?" ;
	Pattern re = Pattern.compile(pattern);

	Matcher m = r.matcher(str);
	if (m.find()){
		return true;
	}
	return false;
}

Char Removal

input: A string and target(s) that needs to be removed.
output: A stirng after remove certain characters.

  • 可以使用 char array, 两个指针 i, j 从左往右扫描, i 的左边不包括 i 都是要保留的, 最后返回 new String(input, 0, i).
  • 或者使用一个 StringBuilder, 一个指针, 如果是需要保留的元素就加到 StringBuilder 里面, 否则跳过.
  • 需要一个额外的数据结构 HashSet 为了可以快速的确认是否是需要被删除的 target.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String removeChar(String str, List<Character> tagert) {
	if (str == null || str.length == 0 || target.size() == 0) {
		return str;
	}

	Set<Character> candidates = new HashSet<>();
	for (Character s : target) {
		candidates.add(s);
	}
	char[] set = str.toCharArray();
	int i = j = 0;
	while (j < set.length) {
		if (!candidates.congtains(set[j])) {
			set[i++] = set[j++];
		} else {
			j++;
		}
	}
	return new String(set, 0, i);
}

Space Removal

input: A string.
output: A string with no leading nor trailing spaces, and leave one space between words.

  • 和 char removal 是一样的, 只是 target 变成了 space.
  • 删除所有的 space 之后, 在不同的单词中间加上一个空格.
  • 这里只需要关注指针 j 的 3 种状态, j == “ “, j != “ “ (j 指向的是单词的首字母, j 指向的是单词的非首字母).

Cases:

  • String with only spaces
  • Leading spaces and trailing spaces

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
public String removeSpace(String str) {
	if (str == null || str.length == 0) {
		return str;
	}
	char[] set = str.toCharArray();
	int i = 0, j = 0;
	while (j < set.length) {
		if (j == " ") {
			j++
		}
	}
}

Left Pad

input: a string, output size, (and a char).
output: new string with size of length fulfill by char/space.

实现一个 leftpad 库. 包含了两种重载的方法.

  1. 有替补字符.
  2. 无替补字符, 则用空格代替.

这是一道随机抽出来的简单题, 还挺好玩儿的. 直接 po 一下代码吧.时间复杂度 O(n), n 是 size. 空间是 O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class LeftPad {
    /**
     * @param originalStr: the string we want to append to with spaces
     * @param size: the target length of the string
     * @return: A string
     */
    public String leftPad(String originalStr, int size) {
        return leftPad(originalStr, size, ' ');
    }

    /**
     * @param originalStr: the string we want to append to
     * @param size: the target length of the string
     * @param padChar: the character to pad to the left side of the string
     * @return: A string
     */
    public String leftPad(String originalStr, int size, char padChar) {
        if (originalStr == null) {
            return null;
        }
        StringBuilder bd = new StringBuilder();
        for (int i = 0; i < size - originalStr.length(); i++) {
            bd.append(padChar);
        }
        return new String(bd + originalStr);
    }
}

LeetCode 266. Palindrome Permutation I

input: a string
output: whehter there exists a palindrome permutation.

本来以为是一道排列组合题, 但是要求返回的是 true or false. 联想一下 palindrome 的特性,

  1. 相同的字母数量一定是偶数的.
  2. 可以有唯一一个单独的存在.

那么其实就可以用打擂台的方式, 用一个 set 就可以了, 反正出现一个相同的就会删除一个. 时间复杂度是 O(n), 空间复杂度是 O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class CanPermutePalindrome {
    /**
     * @param s: the given string
     * @return: if a permutation of the string could form a palindrome
     */
    public boolean canPermutePalindrome(String s) {
        if (s == null) {
            return true;
        }
        //字母和出现的次数
        Set<Character> map = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (map.contains(ch)) {
                map.remove(ch);
            } else {
                map.add(ch);
            }
        }

        return map.size() > 1 ? false : true;
    }
}

LeetCode 267. Palindrome Permutation II

input: a string.
output: return all possible palindrome permutations without duplicates.

虽然这两道题是兄弟吧, 但是差距有点大. 非要搭上点儿联系的话, palindrome permutation I 可以看做是一个预处理. 那么首先要花费 O(n)的时间来判断一下给定的 string 是否能够构成 palindrome. 其次就要 O(n!)的时间深搜找排列了. 第一步的空间复杂度是 O(n), 因为搜索的过程中可能会把全部元素都存放在 set 里面. 第二步的空间复杂度是 O(n/2 + n/2),只考虑一半元素的全排列, 所以还是 O(n).

根据回文的定义, 中心点左右两边的元素是对称的, 所以这里需要考虑两个因素,

  1. 中心元素
  2. 对称元素
    可以像 Left Pad 那道题一样, 如果有中心元素, 则传入中心元素, 否则传入 String (方便直接做 concatenation).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class PalindromePermutationII {
    /**
     * @param s: the given string
     * @return: all the palindromic permutations (without duplicates) of it
     */
    public List<String> generatePalindromes(String s) {
        List<String> result = new ArrayList<>();
        if (s == null) {
            return result;
        }
        //用来判断是否可以成为 palindrome, 以及最后剩余的中心元素是什么
        Set<Character> map = new HashSet<>();
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (map.contains(ch)) {
                map.remove(ch);
                list.add(ch);
            } else {
                map.add(ch);
            }
        }
        if (map.size() > 1) {
            return result;
        }
        String mid = "";
        for (char c : map) {
            mid = c + "";
        }
        //如果 input 已经排好序, 那么就不需要排序了.
        Collections.sort(list);
        helper(list, 0, new StringBuilder(), result, mid, new boolean[list.size()]);
        return result;
    }

    private void helper(List<Character> list, int index, StringBuilder bd, List<String> result, String mid, boolean[] visited) {

        if (bd.length() == list.size()) {
            result.add(new String (bd + mid + bd.reverse().toString()));
            bd.reverse();/////////////这里一定要记得翻转回来, 否则返回上一层的结果是反转过的 string
            return;
        }

        for (int i = 0; i < list.size(); i++) {
            if (visited[i]) {
                continue;
            }
            if (i != 0 && list.get(i) == list.get(i - 1) && !visited[i - 1]) {
                continue;
            }
            bd.append(list.get(i));

            visited[i] = true;
            helper(list, i + 1, bd, result, mid, visited);
            bd.deleteCharAt(bd.length() - 1);

            visited[i] = false;
        }
    }
}

LeetCode 242. Valid Anagram

input: two strings.
output: return whether they are anagram.

Two strings are anagrams if and only if their character counts (respective number of occurrences of each character) are the same.
时间复杂度 O(n), 空间 O(1). 额外数据结构 hashmap<字母, 字母出现个数>.

  1. 把 source 所有元素的个数对应到 map 里面.
  2. 循环 target 所包含的元素, count 对应减 1, 如果 map 里面不包含, 出现次数少于 target 里面字母的出现次数就返回 false.
    两轮时间复杂度是 O(2n), 所以是 O(n). 空间使用了一个 Map, 但是长度是定长的(已知数组只包含小写字母和空格), 空间是 O(26), 所以空间复杂度是 O(1).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class ValidAnagram {
    /**
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if (s == null && t == null) {
            return true;
        }
        if (s == null || t == null) {
            return false;
        }
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            Integer count = map.get(s.charAt(i));
            if (count == null) {
                map.put(s.charAt(i), 1);
            } else {
                map.put(s.charAt(i), count + 1);
            }
        }

        for (int i = 0; i < t.length(); i++) {
            Integer count = map.get(t.charAt(i));
            if (count == null || count == 0) {
                return false;
            }
            map.put(t.charAt(i), count - 1);
        }
        return true;
    }
    private class ValidAnagramTest {
        @Test
        void check() {
            assertEquals(true, isAnagram("ab", "ba"));
            assertEquals(true, isAnagram("happy new year", "n ahwryeypp ea"));
            assertEquals(false, isAnagram("", " "));
        }
    }
}

Java 有一些 cache/pooling 上的优化(尽量减少在 heap 上创建对象), 例如 Integer object -128 ~ 127, 两个相同的 String 等等 1. 所以在比较两个 Object 的值是否相等的时候, 尽量不要用 ==, 而用 .equals
== 如果两边都是 reference, 那么(没有优化的情况下)会比较地址. 如果有一边是 primitive type, 那么就会进行 unboxing/autoboxing.
而+ - * / < > <= >= 则不需要担心, 因为在 Java 中它们只能够被应用在 primitive type 上面, 所以会被自动的 unboxing/autoboxing.

  1. 1.对于 String 来说, 因为它是 immutable 的, 即使做了一个在 cache 上的优化(两个值相同的 varibale 指向了同一个地址), 也不会影响结果. 因为 String 是 immutable 的, 如果对其中一个 varibale 进行了更改(增删操作), 那么系统会重新创建一个对象并且使变量指向这个新的对象的地址. ↩
  2. 2.StringBuilder 和 StringBuffer 最主要的区别就是线程安全, 单线程中不需要 StringBuffer. ↩